package java学习.代码随想录.动态规划.背包;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/10 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class _01_背包 {
    /**
     * 背包最大重量为4。
     *
     * 物品为：
     *
     *       重量	  价值
     * 物品0	  1	       15
     * 物品1	  3	       20
     * 物品2	  4	       30
     * 问背包能背的物品最大价值是多少？
     *   DutyRecordSheet DutyShift值班班次 DutyDate 填报人 attendance duty 班次
     */
    public static int  maxbagValue(int weight[],int value[],int bagsize){
//        dp[i][j] : 0~i 的物品中 在容量为 j 的最大value。
        int [][] dp= new int[weight.length+1][bagsize+1];

//        初始化： i=0 时，value=0; dp[0][j] =0; 没有物品
//              j=0时， dp[i][0] = 0; 此时 背包容量为0；
        for (int i = 0; i <=bagsize; i++) {
            dp[0][i] = 0;
        }
        for (int i = 0; i <=weight.length; i++) {
            dp[i][0] = 0;
        }

        for (int i = 1; i <=weight.length; i++) {
            for (int j = 1; j <=bagsize; j++) {
                if (weight[i-1] > j){
                    dp[i][j] = dp[i-1][j]; // 表示不加入第i-1个物品
                }else {
                    dp[i][j] = Math.max(dp[i-1][j] ,
                            dp[i-1][j-weight[i-1]]+value[i-1] );
                }
//                表示装入 第i-1个物品，
            }
        }

        for (int i = 0; i <=weight.length; i++) {
            for (int j = 0; j <=bagsize; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println(" ");
        }
        return dp[weight.length][bagsize];

    }
    public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
        int wlen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen + 1][bagsize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wlen; i++){
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wlen; i++){
            for (int j = 1; j <= bagsize; j++){
                if (j < weight[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wlen; i++){
            for (int j = 0; j <= bagsize; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

//    oneDimensionalArray 一维数组优化法
    /**
     *      *        重量	  价值
     *      * 物品0	  1	       15
     *      * 物品1	  3	       20
     *      * 物品2	  4	       30
     * 为什么不正序：
     * 1. 若正序，
     * dp[1] = dp[1],dp[1-w[i]]+v[i]   ;w[0]=1  w[1] =3 即： dp[1] = dp[0]+v[0] = 15
     * dp[2] = dp[2] , dp[2-w[i]]+ v[i]; w[0]=1  w[1] =3 即：dp[2] = dp[1]+v[0] = 30 ；
     * 此时dp[2] 又加了一次 物品0，todo 而01背包，每个物品只能放一次。 故不行
     * 为什么 容量要倒序 就可以保证每个物品只放 1 次？
     * 1. 现在是01背包，每个物品只能放一次。
     * 2. dp[2] = dp[2] , dp[2-w[i]]+ v[i]; w[0]=1  w[1] =3 即：dp[2] = dp[1]+v[0] = 15  todo 但此时 dp[1]没有计算，仍是初始值0，
     *    每次都是倒序，就不会重复获取到之前的数据，保证只取一次
     *
     */
    public static int  maxbagValueOne(int weight[],int value[],int bagsize){
        int wl = weight.length;
//        先遍历物品，再遍历容量

        int [] dp = new int[bagsize+1];

        for (int i = 0; i < wl; i++) {
            for (int j = bagsize; j >=weight[i]  ; j--) {
                dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }

        }
        System.out.println(Arrays.toString(dp));
        return dp[bagsize];
    }

    /**
     * 正常情况：
     * [0, 15, 15, 20, 35]
     * 35
     // 颠倒遍历顺序：。
     * -----------
     * [0, 15, 15, 20, 30]
     * 30
     * 发现没，这样的话，一个背包只能放入一个物品 。 一个不是一种。
     */
    public static int  maxbagValueOneReverse(int weight[],int value[],int bagsize){
        int wl = weight.length;
//        先遍历容量，再遍历物品

        int [] dp = new int[bagsize+1];

        for (int j = bagsize; j >=0  ; j--) {
            for (int i = 0; i < wl; i++) {
                if (j>=weight[i]){

                    dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
                }else {
                    dp[j] = dp[j];
                }
        }

        }
        System.out.println(Arrays.toString(dp));
        return dp[bagsize];
    }
        public static void main(String[] args) {

        int[] weight = {1,  3,  4};
        int[] value =  {15, 20, 30};
        int bagsize = 4;
        System.out.println(maxbagValue(weight, value, bagsize));
        System.out.println("-----------");
        testweightbagproblem(weight, value, bagsize);
            System.out.println("-----------");
            System.out.println(maxbagValueOne(weight, value, bagsize));
            System.out.println("-----------");

            System.out.println(maxbagValueOneReverse(weight, value, bagsize));

        }
}
